//
// Created by ade on 2022/10/21.
//

class Solution {
public:
    int largestSumAfterKNegations(vector<int> &nums, int k) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        if (nums[0] >= 0) {
            if (k % 2 == 0) return accumulate(nums.begin(), nums.end(), 0);
            else return accumulate(nums.begin() + 1, nums.end(), 0) - nums[0];
        } else if (nums.back() <= 0) {
            if (len <= k) {
                int sum = -1 * accumulate(nums.begin(), nums.end(), 0);
                if ((k - len) % 2 == 0) return sum;
                else return sum + 2 * nums.back();
            } else {
                return -1 * accumulate(nums.begin(), nums.begin() + k + 1, 0) +
                       accumulate(nums.begin() + k + 1, nums.end(), 0);
            }
        } else {
            for (int i = 0; i < len; i++) {
                if (nums[i] >= 0 || k == 0) break;
                nums[i] = -1 * nums[i];
                k--;
            }
            if (k % 2 == 0) return accumulate(nums.begin(), nums.end(), 0);
            else {
                sort(nums.begin(), nums.end());
                return accumulate(nums.begin(), nums.end(), 0) - 2 * nums[0];
            }
        }
    }

    int largestSumAfterKNegations(vector<int> &nums, int k) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        for (int i = 0; i < len; i++) {
            if (nums[i] >= 0 || k == 0) break;
            nums[i] = -1 * nums[i];
            k--;
        }
        sort(nums.begin(), nums.end());
        // 如果k==0,直接返回和 如果k>0，说明现在全是正数，此时只要k%2==1才会减去第一个，否则也是返回和，合并之后可以将条件转为k%2 == 0
        if (k % 2 == 0) return accumulate(nums.begin(), nums.end(), 0);
        return accumulate(nums.begin(), nums.end(), 0) - 2 * nums[0];
    }
};